/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
 var merge = function(nums1, m, nums2, n) {
    if(nums1[0] == 0 && m == 0){
        let j = 0;
        while(j != n){
            nums1[j] = nums2[j];
            j++;
        }
        return;
    }
    let i = 0;
    while(i != n){
        find(nums1,m,nums2[i]);
        i++;
        m++;
    }
    nums1.splice(m,n);
};


const find = (num1, len, a) => {
    let low = 0;
    let hight = len - 1;
    let mid = 1;
    let found = false;
    if(a<num1[low]){
        mid = 0;
    }else if(a>num1[hight]){
        mid = hight+1;
    }else{
        if(hight > 1){
            while((hight-low) != 1){
                mid = Math.round((hight-low)/2) + low;
                if(a>num1[mid]){
                    low = mid;
                }else if(a<num1[mid]){
                    hight = mid;
                }else{
                    found = true;
                    break;
                }
            }
            if(!found){
                if(mid == low){
                    mid++;
                }
            }
        }
    }
    num1.splice(mid,0,a);
    return;
}